There are many challenges to creating a highly secure computing environment such as preventing eavesdroppers from accessing private communications, preventing vandals from tampering with information while in transit from sender to receiver, authenticating users logging into a network, verifying a network server is indeed the server it professes to be and safeguarding confidential documents from unauthorized individuals. A variety of standards have been developed in order to address these challenges including Secure Sockets Layer (SSL), Secure Electronic Transactions (SET) and Secure Multipart Internet Mail Encoding (S/MIME). These standards are rooted on a common technology: cryptography.
In cryptography, a sender transforms data into an unreadable form, known as encrypting the data, and transmits the data to a receiver, thereby ensuring privacy. The receiver transforms the encrypted information back to readable form by decrypting the data. A commonly employed approach, known as symmetric-key cryptography, uses a single "key" to encrypt and decrypt messages. This approach allows two parties to carry out bidirectional communication using a single key, each party encrypting and decrypting information with the same key. Symmetric-key cryptography, however, suffers from several basic problems. First, the key itself must be securely communicated to other party. Second, each party must trust the other party to adequately safeguard the key. Third, symmetric-key cryptography lacks scalability, i.e., a unique key must be secretly maintained for each communication channel. In other words, if a user wishes to independently communicate with several other individuals, the user must maintain a secret key for each individual, otherwise the individuals could easily snoop on the communications to each other. Thus, symmetric-key cryptography may be a viable option for small networks but quickly becomes inadequate and unwieldy as the number of communication channels proliferates.
Due to the disadvantages of symmetric-key cryptography, many of the current standards mentioned above rely on a different technique known as public key cryptography. Unlike symmetric-key cryptography, public key cryptography uses a pair of asymmetric keys, one for encryption and one for decryption. Each key performs a one-way transformation upon the data. When information is encrypted using one of the keys, it can only be decrypted using the other key. Furthermore, it is computationally impractical, if not impossible, to determine one of the keys based on the other.
In public key cryptography, one of the keys is widely publicized and is known as the public key. The other key, known as the private key, is maintained secretly. To send a secure message, a sender encrypts the message using the recipient's public key and transmits the message to the receiver. The message can be decrypted by the private key known only to the recipient. Thus, public key cryptography does not have the scalability problem of symmetric-key cryptography. Furthermore, public key cryptography does not require the secure communication of a key itself and the receiver need not trust any other party with maintaining a secret key.
An interesting feature of public key cryptography is that a sender can "digitally sign" an outgoing communication by simply reversing the process. For example, a transmission that is encrypted with the sender's private key can only be decrypted using the sender's public key. Thus, the receiver can trust that the communication came from the claimed place of origin if the communication is successfully decrypted using the public key of the place of origin. Because the public key of the claimed sender was used to verify the "digital signature" of the sender, the information must have be encrypted by the sender's private key known only to the sender.
Even though public key cryptography has several advantages over symmetric-key cryptography, encrypting and authenticating digital signatures relies on the validity of the public key. For example, if the public key is maintained in a common repository, a recipient can rely on the authentication of a communication only to the extent that the recipient can rely on the repository. Furthermore, a sender typically attaches its public key to an outgoing communication so the recipient need not retrieve the sender's public key from the repository. Therefore, it is entirely possible for an imposter to encrypt information with their own private key, pretend to be a different sender and attach their own public key to the communication. In order to solve this problem, standards have defined "digital certificates", also known as public-key certificates, that are issued by trusted authorities such as a network administrator or even the government. A digital certificate is used to establish the authenticity of a public key.
A digital certificate typically contains: (1) a name identifying the owner of the certificate, (2) the owner's public key that is to be authenticated, (3) a name identifying the authority that issued the certificate, (4) the certificate authority's digital signature, (5) a validity period and (6) a serial number generated by the certificate authority. Under this approach, the sender of a message attaches its digital certificate to the communication. The recipient of the message uses the certificate to verify that the sender's public key is indeed authentic. This is accomplished by first verifying the certificate authority's digital signature that is encapsulated within the certificate. If the authority's digital signature proves authentic, the recipient can trust the certificate and can authenticate the message using the sender's public key encrypted within the certificate. In this manner, only the public key for the issuing authority need be implicitly trusted.
One advantage of using digital certificates is that a large-scale organization can establish an authentication hierarchy that corresponds to the organization's hierarchical structure, thereby facilitating public key registration and certification. For example, a large corporation may establish an authentication hierarchy having a central group responsible for issuing corporate certificates. The central group may issue certificates to various groups, divisions or business units within the organization such that each group issues certificates to sub-groups, network administrators or individual users. For example, employees working on a marketing team may receive certificates issued by the marketing division. These certificates are authenticated by the marketing division's certificate and a corporate certificate. In this manner, each level of the hierarchy has its own private key and a corresponding digital certificate issued by its parent for authenticating the public key.
Authentication hierarchies provide a highly secure environment, accommodate diverse security groups and allow the issuance and maintenance of certificates to be distributed across the organization. One disadvantage of an authentication hierarchy, however, is that a receiver must authenticate the digital certificates attached to a message in order to fully verify the authenticity of the message. In large organizations, the authentication hierarchy may have many levels, thus requiring many verifications of digital signatures. Verifying a digital signature is computationally intensive and requires calculation and manipulation of very large integers. Furthermore, each authority may promulgate a certificate revocation list (CRL) listing those certificates which have been revoked and are no longer to be trusted. Revocation may occur when a private key is compromised to the public, when an the organization restructures or when an employee is fired. Thus, a receiver must not only authenticate each digital certificate with its issuer, it must verify that the none of the attached certificates have been revoked or expired. For these reasons, many security systems attempt to minimize the impact of the authentication process by primitive caching schemes. For example, some systems only authenticate certificates that have not been authenticated recently, such as within the past twenty four hours. This scheme has the advantages of simplicity and efficiency but is not very secure. Other more sophisticated systems cache the expiration periods for individual items, such as certificates and CRLs, that have been authenticated. When an expired item is replaced by the issuing authority, these systems remove the old item and authenticate the new item as well as all dependent material. This technique is advantageous in the cache is guaranteed to be accurate, but suffers from large computational hits when a certificate or CRL expires or is revoked.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for a verification system which can efficiently authenticate digital certificates issued by an organization having a hierarchy of certification authorities.